1841B - Keep it Beautiful - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
ll mod = (1e9 + 7);
const int maxn = 2e5 + 3;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
ll inv(ll i, ll modi)
{
    return i <= 1 ? i : modi - (long long)(modi / i) * inv(modi % i, modi) % modi;
}

vector<ll> fastfactor(long long n)
{
    vector<long long> factorization;
    for (long long d = 2; d * d <= n; d++)
    {
        while (n % d == 0)
        {
            factorization.push_back(d);
            n /= d;
        }
    }
    if (n > 1)
    {
        factorization.push_back(n);
    }
    return factorization;
}
vector<int> minsieve(int n)
{

    vector<int> is_prime(n + 1, -1);
    is_prime[0] = is_prime[1] = (-2);
    for (int i = 2; i * i <= n; i++)
    {
        if (is_prime[i] == (-1) && (long long)i * i <= n)
        {
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = i;
        }
    }
    return is_prime;
}
vector<bool> sieve(int n)
{

    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n; i++)
    {
        if (is_prime[i] && (long long)i * i <= n)
        {
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
    return is_prime;
}

long long binpow(long long a, long long b, long long m)
{
    a %= m;
    long long res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

ll sq(ll n)
{
    ll l = 1;
    ll r = n;

    ll ans = 0;
    while (l <= r)
    {
        int mid = l + (r - l) / 2;
        if ((1LL * mid * mid) == n)
        {
            return mid;
        }
        else if ((1LL * mid * mid) < n)
        {
            ans = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    return ans;
}



vector<ll> factmod(ll n, ll div)
{
    vector<ll> facts(n + 1, 0);
    facts[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        facts[i] = ((facts[i - 1] % div) * (i % div)) % div;
    }
    return facts;
}

vector<bool> primes;
vector<int> primes1;
vector<ll> factorials;
void pre_process()
{
    //primes=sieve(1e6+1);
    // factorials=factmod(1e6+1,1e9+7);
}

void dfs(vector<vector<int>> &mat, int i, int j, ll &sum, vector<vector<int>> &visited)
{
    int m = mat.size();
    int n = mat[0].size();
    if (i < 0 || j < 0 || i > m - 1 || j > n - 1)
    {
        return;
    }
    if (mat[i][j] == 0 || visited[i][j] > 0)
    {
        return;
    }
    visited[i][j] += 1;
    sum += mat[i][j];
    dfs(mat, i, j - 1, sum, visited);
    dfs(mat, i, j + 1, sum, visited);
    dfs(mat, i - 1, j, sum, visited);
    dfs(mat, i + 1, j, sum, visited);
}
long long binomial_coefficient(int n, int k)
{
    if (n < k || k < 0)
    {
        return 0;
    }
    return factorials[n] * inv(factorials[k] * factorials[n - k] % mod, mod) % mod;
}
bool check(ll t,multiset<int> mc){
    
        for(int i=t;i>=1;i--){
            if(*mc.begin()>i || mc.empty()){
                return false;
            }
            auto it=mc.end();
            it--;
            if(*it>i){
                while(*it>i){
                    it--;
                }
            }
           // cout<<"erased "<<*it<<"\n";
            int erased=*it;

            mc.erase(it);
            
            if(mc.empty() && i!=1){
                return false;
            }
            if(mc.empty() && i==1){
                return true;
            }
            //3

            //1 2 2
            int incre=*mc.begin();
            mc.erase(mc.begin());
            mc.insert(incre+i);
            
            

        }
        return true;
    
    }

void solve()
{   
    
        vector<int> v;
        int n;
        cin>>n;
        string s;
        //cin>>s;
        int done=-1;
        for(int i=0;i<n;i++){
            int q;
            cin>>q;
            if(v.size()==0){
                v.push_back(q);
                s+='1';
            }
            else if(v.back()<=q && done==-1){
                v.push_back(q);
                s+='1';
            }
            else if(q<=v.front() && done==-1){
                v.push_back(q);
                done=q;
                s+='1';
            }
            else if((done!=-1) && (q>=v.back()) && (q<=v.front())){
                v.push_back(q);
                s+='1';
            }
            
            
            
            else{
                s+='0';
            }
            /*for(auto it:v){
                cout<<it<<" ";
            }
            cout<<"\n";*/
        }
        cout<<s<<"\n";
        
}
        
    



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    pre_process();
    int t;
    cin >> t;

    while (t--)
    {
        solve();
    }
}